package 贪心;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

public class Zuo会议安排 {
	
	
	/**
	 * 根据  会议的结束时间进行排序, 结束时间 早的 ,先安排. (正确的贪心策略)
	 * @param agendaTime
	 * @return
	 */
	// O(N * lgN )
	public static int greedy(int agendaTime[][]) {
		int ans = 0;
		int deadLine = 0;
		Arrays.sort(agendaTime,(a,b) -> a[1] - b[1]);
		int len = agendaTime.length;
		for(int i = 0;i < len;i++) {
			// 判断当前会议 能不能 被安排
			if(agendaTime[i][0] >= deadLine) {
				ans++;
				// 更新 deadLine
				deadLine = agendaTime[i][1];
			}
		}
		
		return ans;
	}

	/**
	 * 暴力解法: ( 还是全排列问题 )
	 * 这里 其实提供另外一种  回溯过程 中 ,对返回结果的一个思考
	 * 这里先按照 自己最熟悉的 那种 回溯的写法 来写 ,
	 * 然后 再去 coding 另外一种 (将结果作为参数 ,进行传递)
	 */
	public static int solution(int index,int time[][],boolean used[],int deadLine) {
		if(index == time.length) {
			return 0;
		}
		int ans = 0;
		for(int i = 0;i < time.length ;i++) {
			if(used[i]) 
				continue;
			if(time[i][0] >= deadLine) {
				used[i] = true;
				// 下面的 deadLine 要更新 的 
//				ans = Math.max(ans, solution(index + 1,time,used,deadLine) + 1);
				ans = Math.max(ans, solution(index + 1,time,used,time[i][1]) + 1);
				used[i] = false;
			}
			else
				ans = Math.max(ans,solution(index + 1,time,used,deadLine));
			
		}

		return ans;
	}
	
	@Test
	public void testRight() {
		int time[][] = {{0,3},{2,5},{0,5},{1,2},{4,7},{6,10},{5,7}};
		System.out.println(greedy(time));
		boolean used[] = new boolean [time.length];
		System.out.println(solution(0,time,used,0));
	}
	
	/**
	 * 对数器
	 *针对当前题来说
	 *会议的  开始时间  >= 0
	 *结束时间   <= 10000;
	 *数组的长度  10000
	 */
	public static int [][] arraryGenerator(){
		Random random = new Random();
		int size = 10000;
		int [][] arr = new int [size][2];
		int index = 0;
		while(index < size){
			int start = random.nextInt(size);
			int end = random.nextInt(size);
			if(start < end) {
				arr[index][0] = start;
				arr[index][1] = end;
				index ++;
			}
			
		}
		return arr;
	}
	
	public static int [][] arrayGenerator(int arraySize,int maxValue){
		Random random = new Random();
//		int size = 10000;
		int [][] arr = new int [arraySize][2];
//		int index = 0;
		 for(int i = 0;i < arraySize;i++){
			int start = random.nextInt(maxValue);
			int end = random.nextInt(maxValue);
			if(start == end) {
				arr[i][0] = start;
				arr[i][1] = end + 1;
			}
			else {
				arr[i][0] = Math.min(start, end);
				arr[i][1] = Math.max(start, end);
			}
			
		}
		return arr;
	}
	
	
	public static void main(String []args) {
//		for(int i = 0;i < 100; i++) {
//			int arr [][] = arrayGenerator(100,100);
//			boolean used[] = new boolean[100];
//			if(greedy(arr) != solution(0,arr,used,0))
//				System.out.println("fuck! Ego!");
//		}
//		System.out.println("success!");
		
//		for(int i = 0;i < 100;i++ ) {
			boolean used[] = new boolean[10];
			int arr [][] = arrayGenerator(10,100);
			for(int [] i : arr)
				System.out.println(Arrays.toString(i));
//			System.out.println(greedy(arr));
			System.out.println(greedy(arr));
			System.out.println(solution(0,arr,used,0));
//		}
		
		
	}
	
}
